/**
 *  Copyright (C) 2013  Piotr Szczepański
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package edu.pw.elka.gtsna.interaction_index;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import edu.pw.elka.gtsna.graph.Graph;

/**
 * @author Piotr Lech Szczepański
 * @author P.Szczepanski@ii.pw.edu.pl 
 *
 */
public class NaiveII extends InteractionIndex {

    Queue<Integer> queue; 
    Map<Integer, Double> dist;
	
    Map<Integer, Set<Integer>> extNeighbours;
    
    Graph graph;
    
    int k;

    public NaiveII(Graph graph, int k){
    	extNeighbours = new HashMap<Integer, Set<Integer>>();
        dist = new HashMap<Integer,Double>();
        queue = new LinkedList<Integer>();
    	for (int node: graph.getAllNodes()){
    		extNeighbours.put(node, new HashSet<Integer>());
    	}    	

    	this.k = k;
    	this.graph = graph;
    }
 
    protected void singleSourceBFS(int source){
    	extNeighbours.get(source).clear();
        queue.clear();
        
	    for (Integer node: graph.getAllNodes()) {
            dist.put(node, Double.MAX_VALUE);
	    }
	    
	    dist.put(source, 0.0);
	    queue.add(source);
	    
        while (!queue.isEmpty()) {
        	Integer v = queue.poll();
            for(Integer w: graph.getNeigbours(v)){
                if (dist.get(w) == Double.MAX_VALUE ) {
                    dist.put(w, dist.get(v) + 1);
                    extNeighbours.get(source).add(w);
                    if (dist.get(w) < k) {
                    	queue.offer(w);
                    }
                }
            }
        }
    }
    
    private int extDegree(int v){
    	return extNeighbours.get(v).size();
    }
    
    private boolean nodeInScope(int v, int u) {
    	return extNeighbours.get(v).contains(u);
    }
    
    private Set<Integer> extNeigbours (Set<Integer> C){
    	Set<Integer> sum = new HashSet<Integer>();
    	
    	for (int node: C){
			sum.addAll(extNeighbours.get(node));
		}
    	sum.removeAll(C);
    	
    	return sum;
    }
        
    
	/* (non-Javadoc)
	 * @see edu.pw.elka.gtsna.interaction_index.InteractionIndexComputable#interaction(java.util.Set, java.util.Set)
	 */
	@Override
	public double interaction(Set<Integer> C1, Set<Integer> C2) {
		throw new UnsupportedOperationException("Not supported yet.");
	}
	
	@Override
	public void preComputation(){
    	for (int node: graph.getAllNodes()){
    		singleSourceBFS(node);
    	}
	}
	
	@Override
	public double interaction(int v, int u) {
		
		double II = 0.0;

		for (int n: extNeighbours.get(v)) {
			if (extNeighbours.get(u).contains(n)) {
				II++;
			}
		}

		return II;
	}

}
